﻿#pragma once
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

#include <thread>
#include <mutex>
#include <atomic>

#include <assert.h>
#include <time.h>

#include <Windows.h>

using std::cout;
using std::endl;

const static size_t MAX_SIZE = 256 * 1024;
const static size_t MAX_BUCKET = 208;
const static size_t MAX_PAGE = 129;
const static size_t PAGE_SHIFT = 12;

#ifdef _WIN64
typedef unsigned long long PAGE_T;
const static size_t BITS = 64 - PAGE_SHIFT;
#elif _WIN32 
typedef size_t PAGE_T;
const static size_t BITS = 32 - PAGE_SHIFT;

#endif

inline static void* systemAlloc(size_t kpage)
{
	void* ptr = VirtualAlloc(0, kpage << PAGE_SHIFT, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
	assert(ptr);
	return ptr;
}

inline static void systemFree(void* ptr)
{
	VirtualFree(ptr, 0, MEM_RELEASE);
}

static void*& next(void* obj) {
	return *(void**)obj;
}

class freeList {
public:

	void push(void* obj) {
		assert(obj);
		
		next(obj) = _list;
		_list = obj;
		++_size;
	}

	void pushRange(void* start, void* end, size_t n) {
		if (start == nullptr) {
			int a = 1;
		}
		assert(start);
		assert(end);

		next(end) = _list;
		_list = start;

		_size += n;
	}

	void* pop() {
		assert(_list);

		void* obj = _list;
		_list = next(obj);

		--_size;

		return obj;
	}

	void popRange(void*& start, void*& end, size_t n) {
		assert(n <= _size);

		start = _list;
		end = start;
		for (size_t i = 0; i < n - 1; i++) {
			end = next(end);
		}
		
		_list = next(end);
		next(end) = nullptr;

		_size -= n;
	}

	bool empty() {
		return _list == nullptr;
	}

	size_t& getMaxSize() {
		return _maxSize;
	}

	const size_t& size() {
		return _size;
	}
private:
	void* _list = nullptr;
	size_t _maxSize = 1;
	size_t _size = 0;
};

class alignSize {
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128]					8byte对齐	     freelist[0,16)
	// [128+1,1024]				16byte对齐	     freelist[16,72)
	// [1024+1,8*1024]			128byte对齐	     freelist[72,128)
	// [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
	// [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)
public:
	static size_t _align(size_t size, size_t alignNum) {
		return (size + alignNum - 1) & ~(alignNum - 1);
	}

	static size_t align(size_t size) {
		if (size <= 128)
		{
			return _align(size, 8);
		}
		else if (size <= 1024)
		{
			return _align(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _align(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _align(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _align(size, 8 * 1024);
		}
		else
		{
			return _align(size, 8 * 1024);
		}
	}

	// 返回桶下标
	static size_t _index(size_t size, size_t shiftLeft) {
		return ((size + (static_cast<unsigned long long>(1) << shiftLeft) - 1) >> shiftLeft) - 1;
	}

	static size_t index(size_t size) {
		if (size > MAX_SIZE) {
			int a = 0;
		}
		assert(size <= MAX_SIZE);

		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (size <= 128) {
			return _index(size, 3);
		}
		else if (size <= 1024) {
			return _index(size - 128, 4) + group_array[0];
		}
		else if (size <= 8 * 1024) {
			return _index(size - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (size <= 64 * 1024) {
			return _index(size - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0];
		}
		else if (size <= 256 * 1024) {
			return _index(size - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
			return -1;
		}
	}

	// 一次要多少个
	static size_t numOfSize(size_t alignNum) {
		assert(alignNum > 0);
		size_t num = MAX_SIZE / alignNum;

		if (num < 2) {
			num = 512;
		}

		if (num > 512) {
			num = 2;
		}

		return num;
	}

	static size_t numOfPage(size_t alignNum) {
		assert(alignNum > 0);
		size_t num = numOfSize(alignNum);
		size_t nPage = num * alignNum;

		nPage >>= PAGE_SHIFT;
		if (nPage == 0) {
			nPage = 1;
		}
		return nPage;
	}
};

class span {
public:
	PAGE_T _pageId = 0;	// 页下标
	size_t _n = 0;	// 还有多少页

	span* _prev = nullptr;	// 双向链表
	span* _next = nullptr;

	size_t _size = 0;	//	被使用的总大小
	size_t _useCount = 0;	// 已被使用的个数
	void* _freeList = nullptr;	// 自由链表

	bool _use = false;
};

class spanList {
public:
	spanList() {
		_head = new span;
		_head->_prev = _head;
		_head->_next = _head;
	}

	span* begin() {
		return _head->_next;
	}

	span* end() {
		return _head;
	}

	bool empty() {
		return _head == _head->_next;
	}

	void insert(span* pos, span* newSpan) {
		assert(pos);
		assert(newSpan);

		span* prev = pos->_prev;

		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	span* erase(span* pos) {
		assert(pos);
		assert(pos != _head);

		span* prev = pos->_prev;
		span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;

		pos->_next = nullptr;
		pos->_prev = nullptr;

		return pos;
	}

	span* popFront() {
		return erase(begin());
	}

	void pushFront(span* newSpan) {
		insert(begin(), newSpan);
	}
private:
	span* _head;
	
public:
	std::mutex _spanMutex;
};